1.1 Field of the Invention
The present invention generally concerns a hybrid optical and electronic, or optoelectronic, architecture for performing matrix algebraic computations.
The present invention particularly concerns a spatially- and logically-partitioned, expandable, general-purpose, matrix algebraic processing architecture, and certain preferred (i) optoelectronic processor and (ii) optical components for realizing the architecture.
1.2 Description of the Prior Art
Many computational problems can be formalized in terms of matrix algebra. Often these formalisms require the generalization of linear algebraic concepts to include nonlinear or symbolic operations in place of multiplication and summation. Prior architectures for matrix algebraic processing are generally either (i) electronic, or (ii) optical having electronic components only for purposes of delivering data to, and receiving results from, an optically-based computational system.
1.2.1 Previous Electronic Matrix Processors
VLSI electronics can provide the necessary functionality for matrix algebraic processing. However, because of interconnection (wiring) requirements, VLSI suffers from both area inefficiency and high delay for large scale matrix algebraic problems. Matrix algebraic problems are usefully solved by, and in, a hierarchical tree structure of interconnected processing elements (logic circuits). However, an all-electronic matrix algebraic system (a chip) cannot use a particular tree structure called an H-tree for solving an indefinitely large N.times.N matrix problem. This is because the external inputs to the beginning, leaf, processing elements are required to be made through the system (chip) perimeter. The length of this perimeter is on the order of the square root of the dimension N of the matrix (i.e., O(N.sup.1/2)), and cannot support N input lines.
Rather, an all-electronic tree-based matrix algebraic processing system with an external input(s) require a one-dimensional layout, with O(N) line length and O(N.sup.2 logN) area. Area limitations are a major concern for wafer-scale integrated VLSI systems, since the yield of a chip rapidly decreases as e.sup.-TA (assuming no defects can be tolerated), where A is the area of the chip and T is a constant). Reference I. Koren (ed.), Defect and Fault Tolerance in VLSI Systems, Plenum Press 1989.
Accordingly, the practical limitations on the size of a matrix algebraic processing chip or wafer limit both (i) the number of interconnections that can be made to the chip's periphery, and (ii) the number of separate processing elements that even can be connected--let alone be connected at a reasonable line lengths and at reasonable slews in the propagation delays encountered over different connection paths of differing line lengths.
On the other hand, multi-chip VLSI modules can be built with high reliability and low cost, but at the price of increased power dissipation and time delay in propagating signals off-chip.
A conceptual diagram of a semiconductor integrated circuit implementation of a matrix-vector multiplication is illustrated in FIG. 1. An input vector I.sub.e must be electrically distributed to each of the cells of a matrix M.sub.o where, after processing, the result may be electrically extracted from the same matrix M.sub.o as output, or answer, vector O.sub.e. The subscript "e" stands for the electrical nature of the communication, storage, and computational operations.
As stated, the advantages of such a semiconductor-based matrix algebraic processing system include flexible functionality, accurate processing, and a mature, known-cost, technology. The disadvantages include the long propagation delays (i.e., slow computational speed) , and the limited input/output bandwidth of the matrix M.sub.o.
1.2.2 Previous Optical Matrix Arithmetic Processors
Existing optical matrix processors substantially avoid the area and delay penalties inherent to electronics but suffer from low accuracy and limited generality since they rely on (primarily linear) optical phenomena. Reference W. T. Rhodes, Optical Matrix-Vector Processors: Basic Concepts, Proc. SPIE 614, pp 146-152, 1986. In addition, these architectures are often limited in size due to their reliance on a large number of light transmitters (modulators or sources).
A conceptual diagram of an optical implementation of a matrix-vector multiplication is illustrated in FIG. 2. An input vector I.sub.o must be distributed to each of the cells of a matrix M.sub.o where, after processing, the result may be extracted from the same matrix M.sub.o as output, or answer, vector O.sub.o. The subscript "o" stands for the optical nature of the communication and computational operations. The storage of matrix data within the matrix M.sub.o may be optical or electrical.
The advantages of such an optically-based matrix algebraic processing system include low propagation delays (i.e., fast computational speed), and a high, parallel, input/output bandwidth of the matrix M.sub.o. The disadvantages include limited functionality, limited accuracy, and light transmitters--expensive components that are difficult of fabrication in monolithic integrated circuit technologies, especially silicon--that are of the order of N.sub.2 in number (O[N.sup.2 ]) where N is the dimension of the matrix M.sub.o.
1.2.3 Hybrid Electronic and Optical Processors
Because data is often delivered to, and extracted from, optical processing systems by electronic means, hybrid processing systems have been suggested. However, such systems commonly start with electro-optic modulators that optically encode data, proceed to accomplish all algebraic processing optically at high speed, and, finally, detect the optically-encoded results with optoelectronic detectors.
However, any more intimate, or more involved, hybridization of (i) electronics and (ii) optics in a single machine (whether for matrix algebraic processing or otherwise) has been stymied by difficulties in economically communicating across the boundary between electronics and optics. In particular, optical detectors may be fabricated of silicon, and are compatibly made on the same silicon substrates otherwise containing digital logic circuitry. Accordingly, the boundary from electronics, and electrically-encoded signals, to optics, and optically-encoded signals, is not troublesome. However, despite intensive and wide-ranging attempts for over a decade, there has been only very limited progress to the present (1991) in making light transmitters compatibly with silicon-based logic circuitry. Accordingly, the boundary from optics, and optically-encoded signals, to electronics, and electrically-encoded signals, is troublesome.
Because of the speed advantages of optics in both (i) signal communication and (ii) signal processing (including operations like summation and multiplication) recited in section 1.2 above, and because of the difficulty and expense of getting from the electrical domain back into the optical domain, there has been little enthusiasm for truly, and deeply, hybrid electro-optic and optoelectronic systems having much cross-connecting and cross-communicating of optical, and electrical, signals.
1.2.4 The Utility of Foregoing the Speed of Optics In Order to Perform Selective Functions Electrically in a Hybrid Optical and Electronic Matrix Algebraic Processing System
As mentioned in Section 1.2 above, optics has difficulty in achieving high accuracy, although possible solutions to this problem have been proposed. Reference Rhodes, infra. Meanwhile, VLSI circuit electronics is reliably and economically reproducible, and rock solid in performance. Moreover, it is extremely flexible, and can readily be tailored into processing elements that perform any desired arithmetic or logical (i.e., algebraic) operation. Of course electronic circuitry takes a finite time to perform calculations while optics functions significantly faster at the speed-of-light.
As will be seen, the present invention contemplates using electronics, with all its accuracy and reliability and repeatability and economy, to do what electronics does well (albeit relatively slowly): calculations. Furthermore, the present invention contemplates distributing data to the electronics by optical means, thereby alleviating the communications bottleneck of an all-electronic matrix processing system. However, merely partitioning a matrix algebraic problem between optics and electronics in this manner would not invariably be expected to give good results. Indeed, such a partitioning might well result, if crudely performed, in a somewhat cumbersome, and potentially weird, system architecture. In such an architecture certain tasks such as calculation would seemingly be performed in the wrong domain. Meanwhile, necessary information interchange between optical and electrical domains might causes significant time and/or cost penalties.
Accordingly, it is not simply sufficient to declare, in the manner of the King of Hearts from Lewis Carroll's Alice in Wonderland, that certain matrix algebraic processing functions will be performed in a one of the optical or electrical domains, and other functions in the other domain. It would be useful that, if the electronics is to perform certain primitives, such as summation, involved in matrix algebraic calculations, that such electronics should be structured so as to permit, by use of only quite normal semiconductor technology, that line lengths should be exceedingly short and regular, and that clock speeds should accordingly be very fast, producing on the order of one complete calculation per microsecond.
Any small, regular, fast electronic processing elements so functioning would seemingly put a great burden on the optical data distribution. Such an optical data distribution would have to distribute data from and to the electronic processing elements at a breakneck pace. Moreover, when the data is delivered from an electronic processing element in the electrical domain onto an optical data distribution path then a transmitter of light--an object that is difficult of integration and high in cost--is required.
FIGS. 3 and 4 are conceptual representations of alternative, electronic, architectures to the optoelectronic architecture of the present invention whereas FIG. 5 is a conceptual representation of the optoelectronic architecture of the present invention (to be discussed). In the FIG. 3 architecture, a vector is received electrically into each of the cells of an electrical matrix. The cells of the matrix electrically perform a matrix-vector multiplication (or other algebraic operations) on the electrically-received vector, electrically sum the results, and transmit the result vector electrically. The convention of the illustration is thus that the electrical elements are both shown as squares containing a dot, or bullet, or .cndot., and as squares containing a plus sign, or +. The area of the processing system is of the order of N.sup.2 (O[N.sup.2 ]) and the delay is of the order of N (O[N]). Because the architecture depicted in FIG. 3 is an all-electrical, VLSI circuit, embodiment of an matrix algebraic processor, this architecture is prior art.
Although, to the best knowledge of the inventors, it has not been so envisioned, it might be contemplated that one or more optical data distributions should respectively replace the (i) input, and/or (ii) output, electronic data distributions of the electronic, VLSI, matrix algebraic processor architecture shown in FIG. 3. (Such a hybrid architecture would not be prior art.) This would, however, be quite cumbersome. In particular, the number of output light transmitters is of the order of N.sup.2 (O[N.sub.2 ]). In particular, the optical paths would have to be worked out so that certain light-receiving and light-transmitting elements are not in each others shadow(s) .
FIG. 4 shows a similar representation to FIG. 3. An input vector is electrically received into a VLSI circuit matrix, summed electrically in a tree structure of summing nodes, and transmitted electrically. An advantage of the architecture of FIG. 4 over the architecture of FIG. 3 is a reduction in the number of required output signal lines. The area of the processing system is of the order of N.sup.2 LogN (O[N.sup.2 Log.sub.2 N]) and the delay is again of the order of N (O[N]). Because the architecture depicted in FIG. 4 is an all-electrical, VLSI circuit, embodiment of an matrix algebraic processor, this architecture is prior art.
Again, and although to the best knowledge of the inventors it has not been so envisioned it might be envisioned that one or more optical data distributions should respectively replace the (i) input, and/or (ii) output, electronic data distributions of the electronic, VLSI, matrix algebraic processor architecture shown in FIG. 4. (Such a hybrid architecture would not be prior art.) The number of output light transmitters is beneficially reduced to be of the order of N (O[N]) . Again, however, the light paths are uncertain, and the use of electrical distributions in lieu of optical distributions engenders congestion, and inefficient use of area.
In a preview of the architecture of the present invention shown in FIG. 5 the input vector is received optically, algebraically processed electrically including by summation in electrical summing nodes, and then transmitted optically. (According to the fact that FIG. 5 shows a preview of the architecture of the present invention, it does not show prior art.) The area of the processing system is of the order of N.sup.2 (O[N.sup.2 ]), or roughly the same as the all-electronic architecture of FIG. 3, but the delay is reduced to be of the order of .sqroot.N (O[.sqroot.N]). Notably, and as will be explained, both (some) input and (most) output data distributions are optical, and via light. Meanwhile, electrical processing within an tree structure of electrical elements beneficially reduces the number of required output light transmitters to be of the order of N (O[N]) .
Accordingly, there exist many different possibilities for all-electrical, and for hybrid electrical and optical (optoelectronic), matrix algebraic processors/processing systems. If an intimately, and closely, hybridized optical and electronic matrix algebraic processing system is--nonetheless to (i) performing some functions (e.g., calculation) in poor places (e.g., in electronics) and (ii) making large demands upon other certain other functions (e.g , optical data distribution)--to exhibit high performance then careful thought, and careful system architectural organization, is clearly required. It is the forte of the present invention that, a functional partition between electronics and optics having been made somewhat arbitrarily in accordance with the conventional wisdom, a matrix algebraic processing system is nonetheless realized that is both (i) readily presently practically implementatable with existing technology, and (ii) comparable in performance with purely theoretical systems within the literature. This system is next discussed.